package de.infotheo;

import java.math.BigInteger;

public class Gruppentafel {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		System.out.println(new BigInteger("6").modPow(new BigInteger("18"), new BigInteger("8101")).modInverse(new BigInteger("8101")));
		
		int a = 3;
		
//		printAllePotenzen(new String[]{"2","2"}, new String[]{"2","2"}, a, 5, 9);
		
		
		String[][] gruppentafel = erzeugeGruppenTafel(new String[]{"o","3,2","3,3","4,2","4,3"}, 5, a);
		
		for (int i = 0; i<gruppentafel.length; i++){
			System.out.println();
			for (int j = 0; j<gruppentafel.length; j++){
				System.out.print(gruppentafel[i][j]+"   ");
			}
		}
		
	}

	public static String[][] erzeugeGruppenTafel(String[] gruppe, int koerper, int a){
		String [][] gruppentafel = new String[gruppe.length][gruppe.length];
		
		for (int i = 0; i<gruppe.length; i++){
			for (int j = 0; j<gruppe.length; j++){
				
				if(gruppe[i].equals("o") && gruppe[j].equals("o")){
					gruppentafel[i][j] = "o";
				}else if (gruppe[i].equals("o")){
					gruppentafel[i][j] = gruppe[j];
				}else if (gruppe[j].equals("o")){
					gruppentafel[i][j] = gruppe[i];
				}else{
					String[] x1y1 = gruppe[i].split(",");
					String[] x2y2 = gruppe[j].split(",");
					
					int x1 = Integer.valueOf(x1y1[0]);
					int y1 = Integer.valueOf(x1y1[1]);
					int x2 = Integer.valueOf(x2y2[0]);
					int y2 = Integer.valueOf(x2y2[1]);
					
					int x3 = 0;
					int y3 = 0;
					
					if (x1==x2 && y1==-y2){
						gruppentafel[i][j] = "o";
					}else if (x1!=x2){
						int m = mod((y2-y1)*modInverse(x2-x1, koerper), koerper);
						
						x3 = mod((m*m)-(x1+x2),koerper);
						y3 = mod(((-m)*(x3-x1))-y1,koerper);
						
						gruppentafel[i][j] = x3+","+y3;
					}else if (x1==x2 && y1==y2 && y1!=0){
						int m = mod((3*(x1*x1) + a)*modInverse(2*y1, koerper), koerper);
						
						x3 = mod((m*m)-(x1+x2), koerper);
						y3 = mod(((-m)*(x3-x1))-y1,koerper);
						
						gruppentafel[i][j] = ""+x3+","+y3;
					}else{
						gruppentafel[i][j] = "o";
					}
					
					
				}
				
			}
		}
		
		return gruppentafel;
	}
	
	public static void printAllePotenzen(String[] x1y1, String[] x2y2, int a, int koerper, int lauf){
		if (lauf > 0){
			if (x2y2[0].equals("o")){
				System.out.println(x1y1[0]+","+x1y1[1]);
				printAllePotenzen(x1y1, x1y1, a, koerper, lauf-1);
			}else{
				
				int x1 = Integer.valueOf(x1y1[0]);
				int y1 = Integer.valueOf(x1y1[1]);
				int x2 = Integer.valueOf(x2y2[0]);
				int y2 = Integer.valueOf(x2y2[1]);
				
				int x3 = 0;
				int y3 = 0;
				
				if (x1==x2 && y1==-y2){
					System.out.println("o");
					printAllePotenzen(x1y1, new String[]{"o"}, a, koerper, lauf-1);
				}else if (x1!=x2){
					int m = mod((y2-y1)*modInverse(x2-x1, koerper), koerper);
					
					x3 = mod((m*m)-(x1+x2),koerper);
					y3 = mod(((-m)*(x3-x1))-y1,koerper);
					
					System.out.println(x3+","+y3);
					printAllePotenzen(x1y1, new String[]{""+x3,""+y3}, a, koerper, lauf-1);
				}else if (x1==x2 && y1==y2 && y1!=0){
					int m = mod((3*(x1*x1) + a)*modInverse(2*y1, koerper), koerper);
					
					x3 = mod((m*m)-(x1+x2), koerper);
					y3 = mod(((-m)*(x3-x1))-y1,koerper);
					
					System.out.println(x3+","+y3);
					printAllePotenzen(x1y1, new String[]{""+x3,""+y3}, a, koerper, lauf-1);
				}else{
					System.out.println("o");
					printAllePotenzen(x1y1, new String[]{"o"}, a, koerper, lauf-1);
				}
				
				
			}
		}
	}
	
	public static int modInverse(int a, int n) {
		
		a = mod(a, n);
		
		 int i = n, v = 0, d = 1;
		 while (a>0) {
		  int t = i/a, x = a;
		  a = i % x;
		  i = x;
		  x = d;
		  d = v - t*x;
		  v = x;
		 }
		 v %= n;
		 if (v<0) v = (v+n)%n;
		 return v;
		}
	
	// positiver Rest
		public static int mod(int a, int b)
		{
		    int x=a%b;
		    return (x+b)%b;
		}
	
}
